package com.zhupf.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhupf
 * @date 2023年12月26日 16:49
 * @Description
 *
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 */
public class GenerateParenthesis {

    private static List<String> ans = new ArrayList<>();

    private static int leftSize = 0;

    private static int rightSize = 0;

    public static void main(String[] args) {
        generateParenthesis(3);
    }

    public static List<String> generateParenthesis(int n) {
        StringBuffer sb = new StringBuffer();
        if(n == 0){
            return ans;
        }
        dfs(1,n,sb);
        return ans;

    }

    private static void dfs(int k ,int n , StringBuffer sb){
        if(rightSize > leftSize || leftSize > n){
            return;
        }
        if(k == 2*n+1){
            if(leftSize == rightSize){
                ans.add(sb.toString());
            }
            return;
        }
        sb.append("(");
        leftSize++;
        dfs(k+1,n,sb);
        sb.deleteCharAt(sb.length()-1);
        leftSize--;
        sb.append(")");
        rightSize++;
        dfs(k+1,n,sb);
        sb.deleteCharAt(sb.length()-1);
        rightSize--;
    }

}
